public class SelectionSort {

    private SelectionSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        // arr[0..i)是有序的，arr[i..n)是无序的
        for(int i = 0; i < arr.length; i++){
            // 选择arr[i..n) 中最小值的索引
            int minIndex = i;
            for(int j = i ;j < arr.length; j++){
                if(arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;
            }
            swap(arr,i,minIndex);
        }
    }

    public static <E extends Comparable<E>> void sort2(E[] arr){
        // arr[0..i)是无序的，arr[i..n)是有序的
        for(int i = arr.length-1; i >= 0; i--){
            // 选择arr[i..n) 中最大值的索引
            int maxIndex = i;
            for(int j = i ;j >= 0 ; j--){
                if(arr[j].compareTo(arr[maxIndex]) > 0)
                    maxIndex = j;
            }
            swap(arr,i,maxIndex);
        }
    }

    private static <E> void swap(E[] arr, int i, int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;

    }

    public static void main(String[] args){
        // 修改为Integer
        Integer[] arr = {1,4,2,3,6,5};
        SelectionSort.sort(arr);
        for(int e:arr)
            System.out.print(e + " ");
        System.out.println();

        // 新的测试用例
        StudentSelection[] students = {new StudentSelection("Alice",98),
                                       new StudentSelection("Bobo",100),
                                       new StudentSelection("Charles",90)};
        SelectionSort.sort(students);
        for(StudentSelection student:students)
            System.out.println(student + " ");

        // 随机数组的使用
        int[] dataSize = {10000, 100000};
        for(int n:dataSize) {
            Integer[] arr2 = ArrayGenerator.generateRandomArray(n, n);
            SortingHelper.sortTest("SelectionSort", arr2);
        }
    }
}
